/*
	MIDAS Context Based Routing
	cbr_context_model.cc
	Copyright (c) 2007 Radoslaw Olgierd Schoeneich
	MEAG IT PW
*/

#include <string>
#include <stdio.h>
#include <sstream>
#include <set>
#include <queue>
#include "cbr_matrix.h"
#include "cbr_context_model.h"
#include "cbr_debug.h"
#include "cbr_crt.h"

extern bool local_context_model;

/**
 * Parses CBR Context Model configuration file.
 *
 * @param input input I/O stream
 *
 * @return "true" if configuration file was successfully parsed,
 * "false" otherwise.
 */

bool cbr_ContextModel::parse(std::istream& input)
{
	std::istringstream converter;
	std::string buff;

	if (num_concepts != 0) {
		// flush old contents
		if (concepts != NULL)
			delete[] concepts;
		if (concepts_graph != NULL)
			delete[] concepts_graph;
		concepts_map.clear();
		num_concepts = 0;
	}

	do {
		std::getline(input, buff);
	} while (buff.empty() || buff.at(0) == '#');
	converter.str(buff);
	converter >> num_concepts;
	if (num_concepts < 1)
		return false;

	concepts = new std::string[num_concepts];
	concepts_graph = new cbr_Matrix<int>(num_concepts);
	concepts_graph->fill(0);

	cbr_debug("parsing concept model description file\n");
	for (int i = 0; i < num_concepts; i++) {
		int id, a, b;

		do {
			std::getline(input, buff);
		} while (buff.empty() || buff.at(0) == '#');

		converter.clear();
		converter.str(buff);
		converter >> id;
		if (id < 0 || id >= num_concepts || !concepts[id].empty())
			return false;

		converter >> concepts[id];
		if (concepts[id].empty() || concepts_map.count(concepts[id]))
			return false;

		if (id == 0 && concepts[id] != "Thing")
			cbr_log("CONTEXT: 'Thing' has non-zero index!\n");

		concepts_map[concepts[id]] = id;
		//cbr_debug("  concept no. %d: '%s'\n", id, concepts[id].c_str());

		while (converter >> a >> b) {
			if (a < 0 || a >= num_concepts || a == id)
				return false;
			(*concepts_graph)[id][a] = b;
			(*concepts_graph)[a][id] = -b;
			//cbr_debug("  graph edge from %d to %d has weight %d\n",
			//	  id, a, b);
		}
	}

	countCommonSuperClasses();

	return true;
}

/**
 * CBR Context Model destructor.
 */

cbr_ContextModel::~cbr_ContextModel()
{
	if (concepts_graph != NULL)
		delete concepts_graph;
	if (common_superclasses != NULL)
		delete common_superclasses;
	if (concepts)
		delete[] concepts;
}

/**
 * Gets edge weight between two concepts.
 *
 * @param a index of the first concept
 * @param b index of the second concept
 *
 * Gets edge weight between two concepts given their indexes
 * into concepts_graph[][] table.

 * @return edge weight between two concepts.
 */

int cbr_ContextModel::getEdgeWeight(int a, int b) const
{
	int weight = (*concepts_graph)[a][b];
	return (weight >= 0) ? weight : 0;
}

/**
 * Gets sub-concepts of the given concept.
 *
 * @param concept CBR concept
 * @param set CBR concepts set
 */

void cbr_ContextModel::getSubClasses(const cbr_Concept& concept, cbr_ConceptsSet& set) const
{
	// standard breadth-first graph search
	std::queue<int> q;
	std::set<int> visited;
	int i, node;

	set.clear();

	concepts_map_t::const_iterator starting_node=concepts_map.find(concept);
	if (starting_node == concepts_map.end())
		return;

	q.push(starting_node->second);
	while (!q.empty()) {
		node = q.front();
		q.pop();
		visited.insert(node);

		for (i = 0; i < num_concepts; i++) {
			if ((*concepts_graph)[node][i] > 0 && visited.count(i) == 0)
				q.push(i);
		}
	}

	std::set<int>::iterator v = visited.begin();
	while (v != visited.end()) {
		set.insert(concepts[*v]);
		v++;
	}
}

/**
 * Gets super-concepts of the given concept.
 *
 * @param concept CBR concept
 * @param set CBR concepts set
 */

void cbr_ContextModel::getSuperClasses(const cbr_Concept& concept, cbr_ConceptsSet& set) const
{
	if (local_context_model == false)
		return cbr_getSuperClasses(concept, set);

	// standard breadth-first graph search
	std::queue<int> q;
	std::set<int> visited;
	int i, node;

	set.clear();

	concepts_map_t::const_iterator starting_node=concepts_map.find(concept);
	if (starting_node == concepts_map.end())
		return;

	q.push(starting_node->second);
	while (!q.empty()) {
		node = q.front();
		q.pop();
		visited.insert(node);

		for (i = 0; i < num_concepts; i++) {
			if ((*concepts_graph)[node][i] < 0 && visited.count(i) == 0)
				q.push(i);
		}
	}

	std::set<int>::iterator v = visited.begin();
	while (v != visited.end()) {
		if (*v != starting_node->second && *v != 0) {
			set.insert(concepts[*v]);
		}
		v++;
	}
}

/**
 * Gets number of common super-concepts of the two given concepts.
 *
 * @param c1 first CBR concept
 * @param c2 second CBR concept
 *
 * @return number of common @a c1 and @a c2 super-concepts.
 */

int cbr_ContextModel::getCommonSuperClassesCount(const cbr_Concept& c1,
						 const cbr_Concept& c2) const
{
	if (local_context_model == false) {
		cbr_ConceptsSet set;

		set.clear();
		cbr_getCommonSuperClasses(c1, c2, set);

		return set.size();
	}

	concepts_map_t::const_iterator i1, i2;

	i1 = concepts_map.find(c1);
	i2 = concepts_map.find(c2);
	if (i1 == concepts_map.end() || i2 == concepts_map.end())
		return 0;
	return (*common_superclasses)[i1->second][i2->second];
}

/**
 * Find the closest common super-concept of the two given concepts.
 *
 * @param c1 first CBR concept
 * @param c2 second CBR concept
 *
 * @return the closest commont super-concept of concepts @a c1 and @a c2
 */

cbr_Concept cbr_ContextModel::findClosestAtomicConcept(const cbr_Concept& c1,
						const cbr_Concept& c2) const
{
	cbr_ConceptsSet set1, set2;
	cbr_ConceptsSet::iterator i1, i2;
	concepts_map_t::const_iterator tmp, closest_common;
	int highest_index = -1;

	getSuperClasses(c1, set1);
	getSuperClasses(c2, set2);

	closest_common = concepts_map.end();
	for (i1 = set1.begin(); i1 != set1.end(); i1++) {
		for (i2 = set2.begin(); i2 != set2.end(); i2++) {
			if (*i1 == *i2) {
				tmp = concepts_map.find(*i1);
				if (tmp->second > highest_index) {
					closest_common = tmp;
					highest_index = tmp->second;
				}
			}
		}
	}

	if (closest_common == concepts_map.end())
		return cbr_Concept("Thing");
	return closest_common->first;
}

/**
 * Gets forwarder(s).
 *
 * @param ca concept based address
 * @param crtable CBR routes table
 * @param mcast multicast flag
 *
 * Gets forwarders set from CBR routes table @crtable given
 * the concept based address @ca.
 *
 * For unicast messages:
 * - get sub concepts of the given concept @ca from the context model
 * - for all sub concepts create list of forwarder id / concept metric pairs
 * - if the list is non-empty return the forwarder with the shortest metric
 * - get super concepts of the given concept @ca from the contect model
 * - for 1st super concept  create list of forwarder id / concept metric pairs
 * - if the list is non-empty return the forwarder with the shortest metric
 * - return empty set
 *
 * For multicast messages:
 * - get sub concepts of the given concept @ca from the context model
 * - get super concepts of the given concept @ca from the contect model
 * - for all concepts create list of forwarder id / concept metric pairs
 * - return set of all forwarders
 *
 * @note this function is needed even when local_context_model == false
 *
 * Called by CBR::recvRequest.
 *
 * @return set of forwarder node ids.
 */

std::set<cbr_ID>* cbr_ContextModel::getForwarders(const cbr_ContextAddress& ca,
			const cbr_CRTable& crtable, bool mcast,
			cbr_ID localID) const
{
	std::list< std::pair<cbr_ID, int> > fl;
//	cbr_debug("getting forwarders for %s\n", ca.getAsString());
	const cbr_ConceptsSet* concepts = ca.getAsSet();
	cbr_ConceptsSet::const_iterator i, j;
	cbr_ConceptsSet tmp;

	cbr_ConceptsSet sub;
	for (i = concepts->begin(); i != concepts->end(); i++) {
		getSubClasses(*i, tmp);

		if (local_context_model)
			getSubClasses(*i, tmp);
		else
			cbr_getSubClasses(*i, tmp);

		cbr_ContextModel::joinSets(sub, tmp);
	}
	for (i = sub.begin(); i != sub.end(); i++)
		crtable.getForwarders(*i, fl, localID);

	if (!mcast && !fl.empty()) {
		// non-empty forwarders list, unicast
		std::list< std::pair<cbr_ID, int> >::iterator f;
		cbr_ID forwarder = 0;
		int shortest_metric = 0x7fffffff;

		for (f = fl.begin(); f != fl.end(); f++) {
			if (f->second < shortest_metric) {
				forwarder = f->first;
				shortest_metric = f->second;
			}
		}

		std::set<cbr_ID>* ret = new std::set<cbr_ID>();
		ret->insert(forwarder);
		return ret;
	} else if (!fl.empty()) {
		// non-empty forwarders list, multicast
		std::set<cbr_ID>* ret = new std::set<cbr_ID>();
		std::list< std::pair<cbr_ID, int> >::iterator f;
		for (f = fl.begin(); f != fl.end(); f++)
			ret->insert(f->first);
		return ret;
	}

	cbr_ConceptsSet sup;
	for (i = concepts->begin(); i != concepts->end(); i++) {

		if (local_context_model)
			getSuperClasses(*i, tmp);
		else
			cbr_getSuperClasses(*i, tmp);

		cbr_ContextModel::joinSets(sup, tmp);
	}
	for (i = sup.begin(); i != sup.end(); i++) {
		if (crtable.getForwarders(*i, fl, localID) && !mcast) {
			break;
		}
	}

	if (!mcast && !fl.empty()) {
		std::list< std::pair<cbr_ID, int> >::iterator f;
		cbr_ID forwarder = 0;
		int shortest_metric = 0x7fffffff;

		for (f = fl.begin(); f != fl.end(); f++) {
			if (f->second < shortest_metric) {
				forwarder = f->first;
				shortest_metric = f->second;
			}
		}

		std::set<cbr_ID>* ret = new std::set<cbr_ID>();
		ret->insert(forwarder);
		return ret;
	}

	std::list< std::pair<cbr_ID, int> >::iterator f;
	std::set<cbr_ID>* ret = new std::set<cbr_ID>();
	for (f = fl.begin(); f != fl.end(); f++)
		ret->insert(f->first);
	return ret;
}

/**
 * Joins two CBR concept sets.
 *
 * @param dst destination CBR concept set
 * @param src source CBR concept set
 */

void cbr_ContextModel::joinSets(cbr_ConceptsSet& dst,
				const cbr_ConceptsSet& src)
{
	cbr_ConceptsSet::const_iterator i;

	for (i = src.begin(); i != src.end(); i++) {
		if (dst.find(*i) == dst.end())
			dst.insert(*i);
	}
}

/**
 * Counts common super-concepts.
 *
 * Counts common super-concepts and stores the results
 * in common_superclasses[] table which is later used
 * by cbr_ContextModel::getEdgeWeight();
 */

void cbr_ContextModel::countCommonSuperClasses()
{
	cbr_ConceptsSet set_i, set_j;
	cbr_ConceptsSet::iterator ii, jj;
	int i, j, cnt;

	common_superclasses = new cbr_Matrix<int>(num_concepts);
	common_superclasses->fill(0);

	for (i = 0; i < num_concepts; i++) {
		for (j = 0; j < num_concepts; j++) {
			getSuperClasses(concepts[i], set_i);
			getSuperClasses(concepts[j], set_j);

			cnt = 0;
			for (ii = set_i.begin(); ii != set_i.end(); ii++) {
				for (jj = set_j.begin(); jj != set_j.end(); jj++) {
					if (*ii == *jj)
						cnt++;
				}
			}
			(*common_superclasses)[i][j] = cnt;
		}
	}
}

/**
 * Gets source(s).
 *
 * @param crtable CBR routes table
 * @param cset concepts set
 * @param localID CBR ID of the local node
 *
 * Gets sources set from CBR routes table @a crtable given
 * the concepts set @a cset.
 *
 * @note this function doesn't support local_context_model == true
 *
 * Called by CBR::getSourcesAll().
 *
 * @return set of source node IDs.
 */

std::set<cbr_ID>* cbr_ContextModel::getSources(const cbr_CRTable &crtable,
						cbr_ConceptsSet &cset,
						cbr_ID localID) const
{
	std::list< std::pair<cbr_ID, int> > fl;
	cbr_ConceptsSet::const_iterator i;

	for (i = cset.begin(); i != cset.end(); i++)
		crtable.getSources(*i, fl, localID);

	std::set<cbr_ID>* ret = new std::set<cbr_ID>();

	if (!fl.empty()) {
		std::list< std::pair<cbr_ID, int> >::iterator f;

		for (f = fl.begin(); f != fl.end(); f++)
			ret->insert(f->first);
	}

	return ret;
}

/**
 * Gets forwarder(s).
 *
 * @param id CBR node id
 * @param crtable CBR routes table
 * @param localID CBR ID of the local node
 *
 * Gets forwarders set from CBR routes table @a crtable given
 * the CBR node ID @a id.
 *
 * @note this function doesn't support local_context_model == true
 *
 * Called by CBR::forward_rreq_with_restrictions().
 *
 * @return set of source node IDs.
 */

std::set<cbr_ID>* cbr_ContextModel::getForwarders(const cbr_ID id,
						const cbr_CRTable &crtable,
						cbr_ID localID) const
{
	std::list< std::pair<cbr_ID, int> > fl;

	crtable.getForwarders(id, fl, localID);

	std::set<cbr_ID>* ret = new std::set<cbr_ID>();

	if (!fl.empty()) {
		std::list< std::pair<cbr_ID, int> >::iterator f;

		for (f = fl.begin(); f != fl.end(); f++)
			ret->insert(f->first);
	}

	return ret;
}
